package 力扣.栈;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

public class 有效的括号20 {
    public static void main(String[] args) {
//        String s = "(())(]";
//        String s = "(]";
//        String s = "()))))))";
        String s = "(";
        boolean valid = isValid2(s);
        System.out.println(valid);
    }

    /**
        栈
        根据栈的性质：先进先出。当我们遇到左括号（如 ‘(’ '[' '{' ）则将其放入栈中，此时我们期望一个右括号（如 ‘)’ ‘]’ '}'）对栈中的元素反向进行抵消
        直到遍历完毕且栈中无元素，则返回true 否则返回false
     */
    public static boolean isValid(String s) {
        Stack<Character> st = new Stack<>();//声明一个栈
        int len = s.length();
        if (len % 2 != 0){
            return false;
        }
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{' ){
                st.push(c);//放入栈顶
            }else {
                if (!st.isEmpty()){
                    Character pop = st.pop();//从栈顶取出
                    char te = 0;
                    //这三个判断语句用来确定栈顶元素和 c 是否匹配
                    if (c == ')'){
                        te = '(';
                    }else if (c == ']'){
                        te = '[';
                    }else {
                        te = '{';
                    }

                    if (pop != te){
                        return false;
                    }
                }else {
                    return false;
                }
            }
        }
        return st.isEmpty();

    }
    public static boolean isValid2(String s) {
        Deque<Character> st = new LinkedList<Character>();//声明一个栈
        HashMap<Character, Character> hashMap = new HashMap<>();
        int len = s.length();
        if (len % 2 != 0){
            return false;
        }
        //使用map代替上面三个判断语句
        hashMap.put(')', '(');
        hashMap.put(']', '[');
        hashMap.put('}', '{');
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{' ){
                st.push(c);//放入栈顶
            }else {
                if (!st.isEmpty()){
                    if (hashMap.get(c) != st.pop() ){
                        return false;
                    }
                }else {
                    return false;
                }
            }
        }
        return st.isEmpty();
    }

    public boolean isValid3(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        if (s.length() %2 != 0){//长度为奇数
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else {//出栈时栈中内容不能为空
                if (c == ')'){
                    if (stack.isEmpty() || stack.pop() != '('){
                        return false;
                    }
                }else if (c == ']'){
                    if (stack.isEmpty() || stack.pop() != '['){
                        return false;
                    }
                }else if (c == '}'){
                        if (stack.isEmpty() || stack.pop() != '{'){
                            return false;
                        }
                }
            }
        }
        return stack.isEmpty() ;
    }
}
